import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/22 17:07
 * @description 思路，从最外围开始dfs。
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] heights = {{1,2,2,3,5},{3,2,3,4,4},{2,4,5,3,1},{6,7,1,4,5},{5,1,1,2,4}};
        solution.pacificAtlantic(heights);
    }

    private boolean[][] canReachP, canReachA;
    private int m, n;

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> ans = new ArrayList<>();
        m = heights.length;
        n = heights[0].length;
        canReachP = new boolean[m][n];
        canReachA = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            dfs(heights, canReachP, i, 0);
            dfs(heights, canReachA, i, n - 1);
        }
        for (int j = 0; j < n; j++) {
            dfs(heights, canReachP, 0, j);
            dfs(heights, canReachA, m - 1, j);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (canReachP[i][j] && canReachA[i][j]) {
                    ans.add(Arrays.asList(i, j));
                }
            }
        }
        return ans;
    }

    public void dfs(int[][] heights, boolean[][] canReach, int i, int j) {
        if (canReach[i][j]) {
            return;
        }
        canReach[i][j] = true;
        // 下一个点的高度比当前节点的海拔高且在区域内，那么说明高出的水能往下流
        if (i > 0 && heights[i - 1][j] >= heights[i][j]) {
            dfs(heights, canReach, i - 1, j);
        }
        if (j > 0 && heights[i][j - 1] >= heights[i][j]) {
            dfs(heights, canReach, i, j - 1);
        }
        if (i + 1 < m && heights[i + 1][j] >= heights[i][j]) {
            dfs(heights, canReach, i + 1, j);
        }
        if (j + 1 < n && heights[i][j + 1] >= heights[i][j]) {
            dfs(heights, canReach, i, j + 1);
        }

    }
}
